#include <stdio.h>
void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

//冒泡排序
void bub(int *a, int n)
{
    for(int i = 0; i < n-1; i++)
    {
        for(int j = 0; j < n-i-1; j++)
        {
            if(a[j] > a[j+1])
                swap(&a[j], &a[j+1]);
        }
    }
}

//选择排序
// 选最小的与第一个交换， 然后 从第二个为未排序的 继续选最小的
void sel(int *a, int n)
{
    for(int i = 0; i < n-1; i++)
    {
        //一开始认为未排序的为第一个
        int min = i;
        for(int j = i+1; j < n; j++)
        {
            if(a[j] < a[min])
                min = j;
        }
        swap(&a[min], &a[i]);
    }
}

//快速排序
//确定基准的位置，保证左边小于基准，右边大于基准
int position(int *a, int left, int right)
{
    int begin = left+1, end = right;
    // 选第一个元素做坑
    int key = a[left];
    // while(begin < end)
    // {
    // }

    while(1)
    {
        while(begin <= end && a[begin] < key) begin++;
        while(begin <= end && a[end] > key)  end--;
        if(begin >= end)  break;
        // 左找大，又找小，begin 和 end 都找到了
        swap(&a[begin], &a[end]);
    }

    // 把key放在合适的位置
    swap(&a[left], &a[end]);
    return end;
}

void quick_sort(int *a, int left, int right)
{
    //递归出口
    if(left < right)
    {
        // 获得基准的位置，把数组划分为2个区域
        int p = position(a, left, right);
        quick_sort(a, left, p-1);
        quick_sort(a, p+1, right);
    }
}

// 插入排序
void Insertsort(int* a, int n)
{
    // 总体思路  [0,end] 有序 将 end+1 的元素数据 插入到[0, end+1]中使有序
    for(int i = 0; i < n-1 ; i++)
    {
        int end = i;
        int tmp = a[end+1];
        while( end>=0 )
        {
            if(tmp < a[end])
            {
                a[end+1] = a[end];
                end--;
            }
            else{
                break;
            }
        }
        a[end+1] = tmp;
    }
}

// 堆排序
// 先建堆，使用向下调整算法建堆，这里建大堆，升序排序
void adjectdown(int* a, int n, int root)
{
    //先假设左子树为大数，找两个子节点中，大的节点与根节点比较
    int parent = root;
    int child = root*2+1;
    // child不能越数组边界，使用while会一直 进行循环直到下面的所有调整之后都为大堆
    while(child < n)
    {
        //如果右子树存在且大于左子树
        if(child+1 < n && a[child] < a[child+1])
        {
            child +=1;
        }
        if(a[parent] < a[child])
        {
            swap(&a[parent], &a[child]);
            parent = child;
            child = 2*parent+1;
        }
        else{
            break;
        }
    }
}

void heapsort(int*a , int n)
{
    //先从最后一个非叶子节点开始建堆
    for(int i = (n-1-1)/2; i >= 0; i--)
    {
        adjectdown(a, n, i);
    }
    //开始交换数据
    int end = n-1;
    while(end >= 0)
    {
        swap(&a[0], &a[end]);
        adjectdown(a, end, 0);
        end--;
    }
}



int main()
{
    int a[5] = {10, 5, 20, 2, 3};
    // bub(a, 5);
    // sel(a, 5);
    // quick_sort(a, 0, 4);
    // Insertsort(a, 5);
    heapsort(a, 5);
    for(int i = 0; i < sizeof(a)/ sizeof(int); i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    return 0;
}
